Approximation Algorithms for Facial Cycles in Planar Embeddings

DOI10.4230/LIPIcs.ISAAC.2018.41OpenAlexW2906860838MaRDI QIDQ5091033

Giordano Da Lozzo, Ignaz Rutter

Publication date: 21 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9989/pdf/LIPIcs-ISAAC-2018-41.pdf/

zbMATH Keywords

complexityapproximation algorithmsplanar embeddingsfacial cycles

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

An SPQR-tree-like embedding representation for upward planarity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms and computation. 25th international symposium, ISAAC 2014, Jeonju, Korea, December 15--17, 2014. Proceedings
• Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time
• Orthogonal graph drawing with inflexible edges
• Embeddings of planar graphs that minimize the number of long-face cycles
• Planarity of streamed graphs
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Drawing Trees, Outerplanar Graphs, Series-Parallel Graphs, and Planar Graphs in a Small Area
• Planar Embeddings with Small and Uniform Faces
• Minimum Edge Dominating Sets
• Determining the Smallest k Such That G Is k-Outerplanar
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Approximation algorithms for NP-complete problems on planar graphs
• Congruent Graphs and the Connectivity of Graphs
• Planar Graphs with Topological Constraints
• Testing Planarity of Partially Embedded Graphs
• Optimal Orthogonal Graph Drawing with Convex Bend Costs

This page was built for publication: Approximation Algorithms for Facial Cycles in Planar Embeddings