A linear algorithm for embedding planar graphs using PQ-trees (Q1083864): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3283487 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3220608 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3883524 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computing an st-numbering / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel concepts in graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Dividing a Graph into Triconnected Components / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient Planarity Testing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5596083 / rank | |||
Normal rank |
Latest revision as of 17:33, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear algorithm for embedding planar graphs using PQ-trees |
scientific article |
Statements
A linear algorithm for embedding planar graphs using PQ-trees (English)
0 references
1985
0 references
This paper presents a simple linear algorithm for embedding (or drawing) a planar graph in the plane. The algorithm is based on the ''vertex- addition'' algorithm of \textit{A. Lempel}, \textit{S. Even}, and \textit{I. Cederbaum} [Theory of graphs, Int. Symp. Rome 1966, 215-232 (1967; Zbl 0197.502)] for the planarity testing, and is a modification of \textit{K. S. Booth} and \textit{G. S. Lueker}'s [J. Comput. Syst. Sci. 13, 335-379 (1976; Zbl 0367.68034)] implementation of the testing algorithm using a PQ-tree. Compared with the known embedding algorithm of \textit{J. E. Hopcroft} and \textit{R. E. Tarjan} [J. Assoc. Comput. Mach. 21, 549-568 (1974; Zbl 0307.68025)], this algorithm is conceptually simple and easy to understand or implement. Moreover this embedding algorithm can find all the embeddings of a planar graph.
0 references
vertex addition algorithm
0 references
linear algorithm
0 references
planar graph
0 references
planarity testing
0 references
embedding algorithm
0 references
0 references