Planar embeddings with small and uniform faces

DOI10.1007/978-3-319-13075-0_50MaRDI QIDQ2942666zbMATH OpenOpenAlexDBLPWikidataFDO

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

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

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: Motivated by finding planar embeddings that lead to drawings with favorable aesthetics, we study the problems MINMAXFACE and UNIFORMFACES of embedding a given biconnected multi-graph such that the largest face is as small as possible and such that all faces have the same size, respectively. We prove a complexity dichotomy for MINMAXFACE and show that deciding whether the maximum is at most $k$ is polynomial-time solvable for $kleq4$ and NP-complete for $kgeq5$. Further, we give a 6-approximation for minimizing the maximum face in a planar embedding. For UNIFORMFACES, we show that the problem is NP-complete for odd $kgeq7$ and even $kgeq10$. Moreover, we characterize the biconnected planar multi-graphs admitting 3- and 4-uniform embeddings (in a $k$-uniform embedding all faces have size $k$) and give an efficient algorithm for testing the existence of a 6-uniform embedding.

Recommendations

• Embeddings of planar graphs that minimize the number of long-face cycles
• Common-Face Embeddings of Planar Graphs
• On the complexity of embedding planar graphs to minimize certain distance measures
• scientific article; zbMATH DE number 1342142
• scientific article; zbMATH DE number 1696626

Cites work

• 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
• Graph Drawing
• Hard tiling problems with simple tiles
• scientific article; zbMATH DE number 177843 (Why is no real title available?)
• scientific article; zbMATH DE number 1342142 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• On the computational complexity of upward and rectilinear planarity testing
• Optimal Orthogonal Graph Drawing with Convex Bend Costs
• Orthogonal graph drawing with flexibility constraints
• Planar embeddings with small and uniform faces
• Spirality and Optimal Orthogonal Drawings
• The complexity of induced minors and related problems

Cited in

(10)

• An SPQR-tree-like embedding representation for upward planarity
• Equilateral drawing of 2-connected planar chordal graphs
• Planar embeddings with small and uniform faces
• Common-Face Embeddings of Planar Graphs
• Planar embeddings with infinite faces
• Approximation Algorithms for Facial Cycles in Planar Embeddings
• Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
• Drawing graphs with k vertices per face: complexity and algorithms
• On the complexity of recognizing k^+-real face graphs
• Embeddings of small generalized polygons

This page was built for publication: Planar embeddings with small and uniform faces

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