Title: A unified approach to testing, embedding and drawing planar graphs
Abstract: Let G = (V,E) be a simple graph. We first consider version of the Hopcroft-Tarjan planarity algorithm that lends itself to exploitation for embedding planar graphs, and subsequently for drawing planar graphs. We describe the algorithms and data structures used to implement the algorithms, and show in particular how embeddings are computed for planar graphs and where the algorithms exit for nonplanar graphs.
An interval representation is a drawing of the graph G in the plane, where vertices are drawn as horizontal intervals and edges are drawn as vertical intervals. We describe algorithms for computing an interval representation for a planar graph using the subgraphs and bridge graphs constructed when testing G for planarity. The paths resulting from the decomposition of G while testing for planarity are mapped to vertical intervals and are uniformly distributed along the x axis. The vertices are spaced uniformly along the y axis according to an st order that also depends on the path decomposition of the graph. The underlying data structures allow for the easy generation of many embeddings of the graph and interactive manipulation of the drawing.
Publication Year: 1991
Publication Date: 1991-05-01
Language: en
Type: article
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot