Planar Embeddings with Small and Uniform Faces

DOI10.1007/978-3-319-13075-0_50zbMath1432.68347arXiv1409.4299WikidataQ62046563 ScholiaQ62046563MaRDI QIDQ2942666

Giordano Da Lozzo, Vít Jelínek, Ignaz Rutter, Jan Kratochvíl

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Approximation Algorithms for Facial Cycles in Planar Embeddings, Book embeddings of \(k\)-framed graphs and \(k\)-map graphs, An SPQR-tree-like embedding representation for upward planarity, Planar Embeddings with Small and Uniform Faces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orthogonal graph drawing with flexibility constraints
• Finding a minimum-depth embedding of a planar graph in \(O(n^{4})\) time
• The complexity of induced minors and related problems
• Embeddings of planar graphs that minimize the number of long-face cycles
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Planar Embeddings with Small and Uniform Faces
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Spirality and Optimal Orthogonal Drawings
• Optimal Orthogonal Graph Drawing with Convex Bend Costs
• Graph Drawing
• Hard tiling problems with simple tiles