On Embedding a Graph in the Grid with the Minimum Number of Bends
From MaRDI portal
Publication:3801098
DOI10.1137/0216030zbMATH Open0654.68090OpenAlexW2002025203MaRDI QIDQ3801098FDOQ3801098
Authors: Roberto Tamassia 
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216030
Recommendations
Computing methodologies and applications (68U99) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Planar graphs; geometric and topological aspects of graph theory (05C10) Applications of graph theory to circuits and networks (94C15)
Cited In (only showing first 100 items - show all)
- Finding a minimum medial axis of a discrete shape is NP-hard
- Towards area requirements for drawing hierarchically planar graphs
- Minimum rectilinear polygons for given angle sequences
- Minimum rectilinear polygons for given angle sequences
- Embedding-preserving rectangle visibility representations of nonplanar graphs
- Octagonal drawings of plane graphs with prescribed face areas
- Algorithms for Drawing Planar p-petal Graphs
- The efficient recognition on net-extensibility of graphs
- Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
- Orthogonal planarity testing of bounded treewidth graphs
- Orthogonal and smooth orthogonal layouts of 1-planar graphs with low edge complexity
- The shape of orthogonal cycles in three dimensions
- Upward drawings of triconnected digraphs.
- The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings
- Greedy rectilinear drawings
- Greedy rectilinear drawings
- INNER RECTANGULAR DRAWINGS OF PLANE GRAPHS
- PSPACE-completeness of an escape problem
- Embedding rectilinear graphs in linear time
- HV-planarity: algorithms and complexity
- Complexity results for three-dimensional orthogonal graph drawing
- An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
- Optimal orthogonal drawings of triconnected plane graphs
- Orthogonal drawing of high degree graphs with small area and few bends
- Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time
- A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
- Relating bends and size in orthogonal graph drawings
- Graph layout for applications in compiler construction
- Drawing graphs on rectangular grids
- New results on drawing angle graphs
- Bend-optimal orthogonal graph drawing in the general position model
- Orthogonal graph drawing with flexibility constraints
- Rectangular grid drawings of plane graphs
- Orthogonal graph drawing with inflexible edges
- Orthogonal graph drawing with inflexible edges
- Embedding problems for paths with direction constrained edges.
- Orthogonal drawings of graphs with vertex and edge labels
- On the complexity of orthogonal compaction
- Lower bounds for planar orthogonal drawings of graphs
- Unit-length rectangular drawings of graphs
- Simultaneous embedding of embedded planar graphs
- Area requirement and symmetry display of planar upward drawings
- NP-completeness for minimizing maximum edge length in grid embeddings
- Non-planar square-orthogonal drawing with few-bend edges
- Three-dimensional orthogonal graph drawing algorithms
- Advances in the theory and practice of graph drawing
- On the density of non-simple 3-planar graphs
- Grid straight-line embeddings of trees with a minimum number of bends per path
- A better heuristic for orthogonal graph drawings
- A note on 3D orthogonal drawings with direction constrained edges
- Efficient automated schematic map drawing using multiobjective mixed integer programming
- Multilayer grid embeddings for VLSI
- Schnyder decompositions for regular plane graphs and application to drawing
- Algorithms for area-efficient orthogonal drawing
- On minimal-node-cost planar embeddings
- Drawing planar graphs using the canonical ordering
- Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract)
- Efficient Algorithms for Ortho-Radial Graph Drawing.
- Planar rectilinear drawings of outerplanar graphs in linear time
- Single bend wiring on surfaces
- Advances on testing C-planarity of embedded flat clustered graphs
- Rectilinear Graphs and Their Embeddings
- A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
- An experimental comparison of four graph drawing algorithms.
- Edge intersection graphs of single bend paths on a grid
- Algorithms for plane representations of acyclic digraphs
- Drawing orders using less ink
- Schematization of networks
- Crossing Layout in Non-planar Graph Drawings
- Crooked diagrams with few slopes
- Strip planarity testing for embedded planar graphs
- Representations of graphs and networks (coding, layouts and embeddings)
- Universal slope sets for 1-bend planar drawings
- Planar L-Drawings of Bimodal Graphs
- Bend-minimum orthogonal drawings in quadratic time
- Vertex contact graphs of paths on a grid
- Graph compact orthogonal layout algorithm
- Proper colorability of segment intersection graphs
- The complexity of iterated reversible computation
- Rectilinear Planarity of Partial 2-Trees
- On turn-regular orthogonal representations
- Orthogonal layout with optimal face complexity
- On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features
- Modifying orthogonal drawings for label placement
- An annotated review on graph drawing and its applications
- Planar Confluent Orthogonal Drawings of 4-Modal Digraphs
- Rikudo is NP-complete
- On the area requirements of planar straight-line orthogonal drawings of ternary trees
- Planar L-drawings of directed graphs
- Planar confluent orthogonal drawings of 4-modal digraphs
- Accelerated bend minimization
- Planar L-drawings of bimodal graphs
- Universal slope sets for upward planar drawings
- How to draw the minimum cuts of a planar graph
- The complexity of Snake and undirected NCL variants
- Orthogeodesic point-set embedding of trees
- Simultaneous orthogonal planarity
- Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
- Bend complexity and Hamiltonian cycles in grid graphs
- Square-orthogonal drawing with few bends per edge
This page was built for publication: On Embedding a Graph in the Grid with the Minimum Number of Bends
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3801098)
