How to draw a planar graph on a grid
From MaRDI portal
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.
Recommendations
Cites work
- A unified approach to visibility representations of planar graphs
- Efficient Planarity Testing
- How to Draw a Graph
- scientific article; zbMATH DE number 3858396 (Why is no real title available?)
- scientific article; zbMATH DE number 3047038 (Why is no real title available?)
- Planar graphs and poset dimension
- Rectilinear planar layouts and bipolar orientations of planar graphs
- Representing a planar graph by vertical lines joining different levels
- Universality considerations in VLSI circuits
Cited in
(only showing first 100 items - show all)- Open rectangle-of-influence drawings of inner triangulated plane graphs
- Small area drawings of outerplanar graphs
- A simple recognition of maximal planar graphs
- Upward straight-line embeddings of directed graphs into point sets
- A polynomial bound for untangling geometric planar graphs
- Visibility representation of plane graphs via canonical ordering tree
- Polychromatic colorings of arbitrary rectangular partitions
- Area requirement and symmetry display of planar upward drawings
- Minimum-width grid drawings of plane graphs
- Advances in the theory and practice of graph drawing
- Grid embedding of 4-connected plane graphs
- Triangulating planar graphs while minimizing the maximum degree
- New results on drawing angle graphs
- Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
- Rectangular grid drawings of plane graphs
- A force-directed algorithm that preserves edge-crossing properties
- Drawing plane triangulations with few segments
- Dushnik-Miller dimension of contact systems of d-dimensional boxes
- Arc diagrams, flip distances, and Hamiltonian triangulations
- \(\mathsf{T}\)-shape visibility representations of 1-planar graphs
- A heuristic approach towards drawings of graphs with high crossing resolution
- Balanced vertex-orderings of graphs
- Planar minimally rigid graphs and pseudo-triangulations
- A result on k-valent graphs and its application to a graph embedding problem
- Incremental convex planarity testing
- Planarity-preserving clustering and embedding for large planar graphs
- Decidability of string graphs
- A left-first search algorithm for planar graphs
- Drawing graphs on rectangular grids
- On a straight-line embedding problem of graphs
- Drawing planar graphs using the canonical ordering
- On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
- Acyclic colorings of graph subdivisions revisited
- A center transversal theorem for hyperplanes and applications to graph drawing
- Approximate proximity drawings
- Straight line embeddings of rooted star forests in the plane
- Crossing number for graphs with bounded pathwidth
- Small universal point sets for \(k\)-outerplanar graphs
- Faster approximate diameter and distance oracles in planar graphs
- Grid straight-line embeddings of trees with a minimum number of bends per path
- From Tutte to Floater and Gotsman: on the resolution of planar straight-line drawings and morphs
- One-bend drawings of outerplanar graphs inside simple polygons
- Limitations on realistic hyperbolic graph drawing
- Tree drawings revisited
- Balanced Schnyder woods for planar triangulations: an experimental study with applications to graph drawing and graph separators
- On the edge-length ratio of planar graphs
- A note on universal point sets for planar graphs
- Homotopy height, grid-major height and graph-drawing height
- Graph stories in small area
- Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs
- Counting polygon triangulations is hard
- Grid drawings of graphs with constant edge-vertex resolution
- On the number of upward planar orientations of maximal planar graphs
- Universal point sets for planar three-trees
- Optimal two-sided embeddings of complete binary trees in rectangular grids
- On a class of covering problems with variable capacities in wireless networks
- The approximate rectangle of influence drawability problem
- Free edge lengths in plane graphs
- Drawings of planar graphs with few slopes and segments
- Area requirement of graph drawings with few crossings per edge
- Orthogeodesic point-set embedding of trees
- Grid representations and the chromatic number
- Skyscraper polytopes and realizations of plane triangulations
- Universal slope sets for 1-bend planar drawings
- On local transformations in plane geometric graphs embedded on small grids
- \(k\)-spine, 1-bend planarity
- A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths
- Rigid realizations of graphs on small grids
- Grid obstacle representation of graphs
- Rectangular partitions of a rectilinear polygon
- The number of Reidemeister moves needed for unknotting
- Intersection graphs of L-shapes and segments in the plane
- Triangulating planar graphs while keeping the pathwidth small
- Mondshein sequences (a.k.a. (2,1)-orders)
- The point-set embeddability problem for plane graphs
- Outer 1-planar graphs
- Non-aligned drawings of planar graphs
- Snapping graph drawings to the grid optimally
- Drawing Graphs on Few Lines and Few Planes
- Bitonic st-orderings for upward planar graphs
- On the density of non-simple 3-planar graphs
- An experimental study on the ply number of straight-line drawings
- Convex drawings of internally triconnected plane graphs on \(O(n^{2})\) grids
- Constrained point-set embeddability of planar graphs
- An effective crossing minimisation heuristic based on star insertion
- scientific article; zbMATH DE number 432759 (Why is no real title available?)
- Improving the minimum-height grid drawings of plane graphs.
- A linear-time algorithm for drawing a planar graph on an (n-2) (n-2) grid.
- On point-sets that support planar graphs
- Small point sets for simply-nested planar graphs
- Approximate proximity drawings
- Computational complexity of motion planning of a robot through simple gadgets
- Straight-Line Grid Drawings of Label-Constrained Outerplanar Graphs with O(n logn) Area (Extended Abstract)
- Succinct Greedy Graph Drawing in the Hyperbolic Plane
- An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges
- Generalizing the Shift Method for Rectangular Shaped Vertices with Visibility Constraints
- Minimum Segment Drawings of Series-Parallel Graphs with the Maximum Degree Three
- Orthogonal cartograms with at most 12 corners per face
- Reprint of: ``Grid representations and the chromatic number
- Upward planar drawings on the standing and the rolling cylinders
This page was built for publication: How to draw a planar graph on a grid
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804582)
