Embedding planar graphs in four pages (Q1120582): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Jozef Širáň / rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56689179 / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jozef Širáň / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0022-0000(89)90032-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2119115989 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The book thickness of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5684962 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Complexity of Coloring Circular Arcs and Chords / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient Planarity Testing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4207598 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sorting Using Networks of Queues and Stacks / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 15:23, 19 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Embedding planar graphs in four pages |
scientific article |
Statements
Embedding planar graphs in four pages (English)
0 references
1989
0 references
A book embedding of a graph is an embedding of the vertices along the spine of a ``book'' (i.e., a linear ordering of the vertices) together with an embedding of its edges on the pages so that edges placed in the same page do not intersect. The author proves that any planar graph has a book embedding with at most four pages. The proof is constructive. Moreover, a linear time algorithm is presented for finding such an embedding. In another paper of the author (which is in preparation), examples of planar graphs are constructed which do not admit a book embedding with 3 pages.
0 references
book embedding
0 references
planar graph
0 references
linear time algorithm
0 references