Symposium on Discrete Algorithms · 1990 · 577 citations · 2 references
Natural SciencesComputer ScienceMathematicsCombinatoricsComputational GeometryGeometric GraphsGraph TheoryGraph EmbeddingsPlanar Graph AlgorithmsPlanar Graphs
We show that each plane graph of order n 2 3 has a straight line embedding on the n-2 by n-2 grid. This embedding is computable in time O(n). A nice feature of the vertex-coordinates is that they have a purely combinatorial meaning.
2
Garry Robert Kampen · Discrete Mathematics · 1976 · 20 citations