How to draw a planar graph on a grid (Q804582): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q57253826, #quickstatements; #temporary_batch_1707337057885 |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:16, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | How to draw a planar graph on a grid |
scientific article |
Statements
How to draw a planar graph on a grid (English)
0 references
1990
0 references
The authors show that every plane graph with n vertices has a straight- line embedding on the 2n-4 by n-2 grid, and provide an O(n) space, O(n.log n) time algorithm for finding the embedding. On the other hand, they prove that any set F, which can support a straight-line embedding of every planar graph of size n, has cardinality at least \(n+(1- o(1))\sqrt{n}\). This settles a problem of B. Mohar.
0 references
planar grid
0 references
planar graph
0 references