1988/02/01 by Daniel Bienstock, Clyde Monma · 4 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #VLSI and FPGA Design Techniques #Advanced Graph Theory Research #Planarity testing #Combinatorics #Planar graph #Mathematics #Book embedding #Time complexity #Embedding #Planar straight-line graph #Discrete mathematics #Graph embedding #Planar #Path graph #Graph #1-planar graph #Graph power #Line graph #Computer science
paper · doi:10.1137/0217004
openalex publication_date 1988/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
The pair (G,D) consisting of a planar graph G = (V,E) with n vertices together with a subset of d special vertices D ⊆ V is called k-planar if there is an embedding of G in the plane so that at most k faces of G are required to cover all of the vertices in D. Checking 1-planarity can be done in linear-time since it reduces to a problem of checking planarity of a related graph. We present an algorithm which given a graph G and a value k either determines that G is not k-planar or generates an appropriate embedding and associated minimum cover in O(ck n) time, where c is a constant. Hence, the algorithm runs in linear time for any fixed k. The fact that the time required by the algorithm grows exponentially in k is to be expected since we also show that for arbitrary k, the associated decision problem is strongly NP-complete, even when the planar graph has essentially a unique planar embedding, d = θ (n), and all facial cycles have bounded length. These results provide a polynomial-time recognition algorithm for special cases of Steiner tree problems in graphs which are solvable in polynomial time.