A left-first search algorithm for planar graphs

DOI10.1007/BF02574056zbMath0826.68090OpenAlexW1989142182MaRDI QIDQ1892422

Hubert de Fraysseix, Patrice Ossona de Mendez, János Pach

Publication date: 2 July 1995

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131374

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (22)

Drawings of planar graphs with few slopes and segments ⋮ On Minimizing One Dimension of Some Two-Dimensional Geometric Representations of Plane Graphs ⋮ A simple proof of the representation of bipartite planar graphs as the contact graphs of orthogonal straight line segments ⋮ Vertex Contact Graphs of Paths on a Grid ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ The Rique-number of graphs ⋮ 4-labelings and grid embeddings of plane quadrangulations ⋮ On Representation of Planar Graphs by Segments ⋮ Bijections for Baxter families and related objects ⋮ Mixed linear layouts: complexity, heuristics, and experiments ⋮ On partitioning the edges of 1-plane graphs ⋮ Extension of a theorem of Whitney ⋮ Orthogonal segment stabbing ⋮ On the number of rectangulations of a planar point set ⋮ On dispersable book embeddings ⋮ Crossing patterns of segments ⋮ Planar bus graphs ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ Planar 3-SAT with a clause/variable cycle ⋮ On mixed linear layouts of series-parallel graphs ⋮ On Mixed Linear Layouts of Series-Parallel Graphs

Cites Work

• How to draw a planar graph on a grid
• Bipartite graphs, upward drawings, and planarity
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• st-ordering the vertices of biconnected graphs
• On grid intersection graphs
• Light sources, obstructions and spherical orders
• Planar lattices and planar graphs
• Computing an st-numbering
• Intersection graphs of curves in the plane
• Bipolar orientations revisited
• Two trees in maximal planar bipartite graphs
• On the Classification of Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A left-first search algorithm for planar graphs