A linear-time algorithm for drawing a planar graph on a grid

DOI10.1016/0020-0190(95)00020-DzbMATH Open0875.68452OpenAlexW2038318850WikidataQ126550591 ScholiaQ126550591MaRDI QIDQ673676FDOQ673676

Authors: Marek Chrobak, Thomas H. Payne 

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00020-d

Recommendations

• A linear-time algorithm for drawing a planar graph on an \((n-2)\times (n-2)\) grid.
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 1990911
• scientific article; zbMATH DE number 2104042
• scientific article; zbMATH DE number 432759

zbMATH Keywords

Algorithms

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Efficient Planarity Testing
• Title not available (Why is that?)
• How to draw a planar graph on a grid
• A unified approach to visibility representations of planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Title not available (Why is that?)
• A linear-time algorithm for drawing a planar graph on a grid
• Drawing planar graphs using the canonical ordering
• How to Draw a Graph
• Title not available (Why is that?)
• Bemerkungen zum Vierfarbenproblem
• Convex Maps
• Title not available (Why is that?)
• Title not available (Why is that?)
• Drawing plane graphs nicely

Cited In (62)

• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• An annotated review on graph drawing and its applications
• Straight-line drawings of 1-planar graphs
• On the complexity of the storyplan problem
• Construction of floorplans for plane graphs over polygonal boundaries
• Convex grid drawings of planar graphs with constant edge-vertex resolution
• A note on the subgraphs of the (\(2\times \infty \))-grid
• A 1.235 lower bound on the number of points needed to draw alln-vertex planar graphs
• Drawing arrangement graphs in small grids, or how to play Planarity
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time
• Small grid drawings of planar graphs with balanced partition
• Optimal polygonal representation of planar graphs
• Drawing arrangement graphs in small grids, or how to play planarity
• The Euclidean bottleneck full Steiner tree problem
• Approximation algorithms for decomposing octilinear polygons
• On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings
• Title not available (Why is that?)
• Grid embedding of 4-connected plane graphs
• On simultaneous straight-line grid embedding of a planar graph and its dual
• Minimum-width grid drawings of plane graphs
• Embedding rectilinear graphs in linear time
• Drawing Planar Graphs with Few Geometric Primitives
• An exponential bound for simultaneous embeddings of planar graphs
• Title not available (Why is that?)
• Graph Drawing
• Planar embedding: linear-time algorithms for vertex placement and edge orderings
• Recognizing and drawing IC-planar graphs
• New results on drawing angle graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• CONVEX GRID DRAWINGS OF FOUR-CONNECTED PLANE GRAPHS
• A linear-time algorithm for drawing a planar graph on a grid
• Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs
• Drawing planar graphs with circular arcs
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• A linear-time algorithm for drawing a planar graph on an \((n-2)\times (n-2)\) grid.
• Small area drawings of outerplanar graphs
• An algorithm for constructing star-shaped drawings of plane graphs
• Grid drawings of graphs with constant edge-vertex resolution
• Title not available (Why is that?)
• Fair redistricting is hard
• A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems
• Convex grid drawings of planar graphs with constant edge-vertex resolution
• The Complexity of Several Realizability Problems for Abstract Topological Graphs
• Optimal point-set embedding of wheel graphs and a sub-class of 3-trees
• Drawing planar graphs using the canonical ordering
• Feedback vertex set on Hamiltonian graphs
• Strictly-convex drawings of 3-connected planar graphs
• Computing cartograms with optimal complexity
• Curve-constrained drawings of planar graphs
• Planar rectilinear drawings of outerplanar graphs in linear time
• Universal slope sets for upward planar drawings
• Metric dimension of maximal outerplanar graphs
• An experimental comparison of four graph drawing algorithms.
• Compact drawings of 1-planar graphs with right-angle crossings and few bends
• Straight-Line Drawing of Quadrangulations
• Arc diagrams, flip distances, and Hamiltonian triangulations
• Title not available (Why is that?)
• SOFSEM 2005: Theory and Practice of Computer Science
• The partial visibility representation extension problem
• CANONICAL DECOMPOSITION, REALIZER, SCHNYDER LABELING AND ORDERLY SPANNING TREES OF PLANE GRAPHS
• Generalizing the Shift Method for Rectangular Shaped Vertices with Visibility Constraints

This page was built for publication: A linear-time algorithm for drawing 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 Q673676)