Planarization of graphs embedded on surfaces

DOI10.1007/3-540-60618-1_66OpenAlexW1517888944MaRDI QIDQ6122212

Hristo N. Djidjev, Shankar M. Venkatesan

Publication date: 28 February 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60618-1_66

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Smaller extended formulations for the spanning tree polytope of bounded-genus graphs

Cites Work

• Finding small simple cycle separators for 2-connected planar graphs
• Edge separators for graphs of bounded genus with applications
• Planar graphs: Theory and algorithms
• Alpha-algorithms for incremental planarity testing (preliminary version)
• The graph genus problem is NP-complete
• A separator theorem for graphs of bounded genus
• Improved constants for some separator theorems
• Node-Deletion NP-Complete Problems
• A Separator Theorem for Planar Graphs
• Edge Separators of Planar and Outerplanar Graphs With Applications
• Efficient Planarity Testing
• An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
• Additivity of the genus of a graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item