1988/01/01 by Hubert de Fraysseix, János Pach, Richard Pollack · 4 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Advanced Combinatorial Mathematics #Embedding #Planar graph #Combinatorics #Book embedding #Mathematics #Cardinality (data modeling) #Planar straight-line graph #Grid #Planar #Graph #Discrete mathematics #Time complexity #Plane (geometry) #Graph embedding #Pathwidth #Line graph #Computer science #Geometry #Artificial intelligence
paper · pdf · doi:10.1145/62212.62254
openalex publication_date 1988/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
Answering a question of Rosenstiehl and Tarjan, we show that every plane graph with n vertices has a Fáry embedding (i.e., straight-line embedding) on the 2n - 4 by n - 2 grid and provide an Ο(n) space, Ο(n log n) time algorithm to effect this embedding. The grid size is asymptotically optimal and it had been previously unknown whether one can always find a polynomial sized grid to support such an embedding. On the other hand we show that any set F, which can support a Fáry embedding of every planar graph of size n, has cardinality at least n + (1 - ο(1)) √n which settles a problem of Mohar.