Approximation Algorithms for Facial Cycles in Planar Embeddings

DOI10.4230/LIPICS.ISAAC.2018.41MaRDI QIDQ5091033zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmscomplexityfacial cyclesplanar embeddings

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Embeddings of planar graphs that minimize the number of long-face cycles
• Planar embeddings with small and uniform faces
• Common-Face Embeddings of Planar Graphs
• Graph embedding with topological cycle-constraints
• Planar Graphs with Topological Constraints

Cites work

• A linear time implementation of SPQR-trees
• Algorithms and computation. 25th international symposium, ISAAC 2014, Jeonju, Korea, December 15--17, 2014. Proceedings
• Approximation algorithms for NP-complete problems on planar graphs
• Congruent Graphs and the Connectivity of Graphs
• Determining the Smallest k Such That G Is k-Outerplanar
• Drawing Trees, Outerplanar Graphs, Series-Parallel Graphs, and Planar Graphs in a Small Area
• Embeddings of planar graphs that minimize the number of long-face cycles
• Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time
• Minimum Edge Dominating Sets
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On the computational complexity of upward and rectilinear planarity testing
• On-line graph algorithms with SPQR-trees
• Optimal orthogonal graph drawing with convex bend costs
• Optimizing over all combinatorial embeddings of a planar graph. (Extended abstract)
• Orthogonal graph drawing with inflexible edges
• Planar embeddings with small and uniform faces
• Planar Graphs with Topological Constraints
• Testing Planarity of Partially Embedded Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(1)

• An SPQR-tree-like embedding representation for upward planarity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091033)