Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing

DOI10.1007/978-3-642-00219-9_29zbMath1213.05055arXiv1110.4881OpenAlexW2133605239MaRDI QIDQ3611864

Vladimir P. Korzhik, Bojan Mohar

Publication date: 3 March 2009

Published in: Journal of Graph Theory, Graph Drawing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.4881

zbMATH Keywords

topological graph1-planar graph1-immersioncrossing edges

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (69)

Outer 1-planar graphs ⋮ Recognizing and drawing IC-planar graphs ⋮ A survey on book-embedding of planar graphs ⋮ Recognizing IC-Planar and NIC-Planar Graphs ⋮ Linear-time recognition of map graphs with outerplanar witness ⋮ \(K_7\)-minors in optimal 1-planar graphs ⋮ On RAC drawings of 1-planar graphs ⋮ Parameterized analysis and crossing minimization problems ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ An annotated bibliography on 1-planarity ⋮ A fast algorithm for the product structure of planar graphs ⋮ On the recognition of fan-planar and maximal outer-fan-planar graphs ⋮ The book thickness of 1-planar graphs is constant ⋮ \(\mathsf{NIC}\)-planar graphs ⋮ A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system ⋮ Proper 1-immersions of graphs triangulating the plane ⋮ On drawings and decompositions of 1-planar graphs ⋮ Right Angle Crossing Graphs and 1-Planarity ⋮ A note on 1-planar graphs ⋮ All 2-planar graphs having the same spanning subgraph ⋮ Maximal 1-plane graphs with dominating vertices ⋮ 1-planarity of complete multipartite graphs ⋮ Weak-dynamic coloring of graphs beyond-planarity ⋮ Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time ⋮ On the edge crossing properties of Euclidean minimum weight Laman graphs ⋮ Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs ⋮ Recognizing optimal 1-planar graphs in linear time ⋮ \(\mathsf{T}\)-shape visibility representations of 1-planar graphs ⋮ Right angle crossing graphs and 1-planarity ⋮ Minimal graphs with respect to geometric distance realizability ⋮ Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs ⋮ 3D Visibility Representations of 1-planar Graphs ⋮ Gap-Planar Graphs ⋮ A linear-time algorithm for testing full outer-2-planarity ⋮ Joins of 1-planar graphs ⋮ Drawing complete multipartite graphs on the plane with restrictions on crossings ⋮ Complexity of Geometric k-Planarity for Fixed k ⋮ A linear-time algorithm for testing outer-1-planarity ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ On partitioning the edges of 1-plane graphs ⋮ The matching extendability of optimal 1-planar graphs ⋮ Light subgraphs in the family of 1-planar graphs with high minimum degree ⋮ Characterizing 5-map graphs by 2-fan-crossing graphs ⋮ Unnamed Item ⋮ Gap-planar graphs ⋮ Ortho-polygon visibility representations of embedded graphs ⋮ Testing gap \(k\)-planarity is NP-complete ⋮ Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing ⋮ Remarks on the joins of 1-planar graphs ⋮ Planar graphs having no proper 2-immersions in the plane. I ⋮ 1-embeddability of complete multipartite graphs on the projective plane ⋮ Crossing numbers of beyond-planar graphs ⋮ Non-1-planarity of lexicographic products of graphs ⋮ Crossing numbers of beyond-planar graphs ⋮ Testing Full Outer-2-planarity in Linear Time ⋮ On 3D visibility representations of graphs with few crossings per edge ⋮ Beyond Planar Graphs: Introduction ⋮ Quantitative Restrictions on Crossing Patterns ⋮ 1-Planar Graphs ⋮ Algorithms for 1-Planar Graphs ⋮ Edge Partitions and Visibility Representations of 1-planar Graphs ⋮ $$\textit{\textbf{k}}$$-Planar Graphs ⋮ 1-planarity testing and embedding: an experimental study ⋮ A Tipping Point for the Planarity of Small and Medium Sized Graphs ⋮ 2-Layer k-Planar Graphs ⋮ Geometric biplane graphs. I: Maximal graphs ⋮ Fan-planarity: properties and complexity ⋮ Counting cliques in 1-planar graphs ⋮ A family of efficient six-regular circulants representable as a Kronecker product

Cites Work

• Unnamed Item
• Unnamed Item
• A linear-time algorithm for 7-coloring 1-plane graphs
• The structure of 1-planar graphs
• Some simplified NP-complete graph problems
• Ein Sechsfarbenproblem auf der Kugel
• Minimal non-1-planar graphs
• Crossing number is hard for cubic graphs
• Approximation Algorithms for Independent Sets in Map Graphs
• Map graphs
• Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
• Zur Struktur 1‐planarer Graphen
• Computing and Combinatorics
• A new proof of the 6 color theorem

This page was built for publication: Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing