Results 11 to 20 of about 3,062 (225)
On a Class of Planar Graphs with Straight-Line Grid Drawings on Linear Area
Journal of Graph Algorithms and Applications, 2009 Summary: A straight-line grid drawing of a planar graph \(G\) is a drawing of \(G\) on an integer grid such that each vertex is drawn as a grid point and each edge is drawn as a straight-line segment without edge crossings. It is well known that a planar graph of \(n\) vertices admits a straight-line grid drawing on a grid of area \(O(n^2)\).
Md. Rezaul Karim, Md. Saidur Rahman
openalex +2 more sources
Edge-Disjoint Homotopic Paths in Straight-Line Planar Graphs [PDF]
SIAM Journal on Discrete Mathematics, 1991 Let G be a planar graph, embedded without crossings in the euclidean plane $\mathbb{R}^2 $, and let $I_1 , \cdots ,I_p $ be some of its faces (including the unbounded face), considered as open sets. Suppose there exist (straight) line segments $L_1 , \cdots ,L_t $ in $\mathbb{R}^2 $ so that $G \cup I_1 \cup \cdots \cup I_p = L_1 \cup \cdots \cup L_t ...
Alexander Schrijver
openalex +2 more sources
Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs [PDF]
, 2013 A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. In general, 1-planar graphs do not admit straight-line drawings. We show that every 3-connected 1-planar graph has a straight-line drawing on an integer grid of quadratic size, with the exception of a single edge on the outer face that has one bend.
Md. Jawaherul Alam +2 more
openalex +2 more sources
A Linear Time Algorithm for Constructing Maximally Symmetric Straight-Line Drawings of Planar Graphs [PDF]
, 2005 This paper presents a linear time algorithm for constructing maximally symmetric straight-line drawings of biconnected and one-connected planar graphs.
Seok-Hee Hong, Peter Eades
openalex +2 more sources
Encompassing colored planar straight line graphs
Computational Geometry, 2007 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Ferrán Hurtado +3 more
openalex +2 more sources
Area-efficient planar straight-line drawings of outerplanar graphs
Discrete Applied Mathematics, 2007 An outerplanar graph \(G\) with \(n\) vertices and maximal degree \(d\) admits a planar straight-line grid drawing with area \(\mathbf O(dn^{1.48})\) in \(\mathbf O(n)\) time. In case \(d=\mathbf o(n^{0.52})\), \(G\) can be drawn this way in \(\mathbf o(n^2)\) area.
Ashim Garg, Adrian Rusu
openalex +3 more sources
Refining a triangulation of a planar straight-line graph to eliminate large angles [PDF]
Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, 2002 We show that any planar straight line graph (PSLG) with v vertices can be triangulated with no angle larger than 7/spl pi//8 by adding O(v/sup 2/log v) Steiner points in O(v/sup 2/log/sup 2/ v) time. We first triangulate the PSLG with an arbitrary constrained triangulation and then refine that triangulation by adding additional vertices and edges.
Scott A. Mitchell
openalex +2 more sources
On the Number of Acute Triangles in a Straight-Line Embedding of a Maximal Planar Graph
Journal of Combinatorial Theory, Series B, 1999 We show that any maximal planar graph with \(m\) triangles except the unbounded face can be transformed into a straight-line embedding in which at least \(\lceil m/3\rceil\) triangles are acute triangles. Moreover, we show that any maximal outer-planar graph can be transformed into a straight-line embedding in which all faces are acute triangles except
Atsushi Kaneko +2 more
openalex +2 more sources
O( n log log n )-work parallel algorithms for straight-line grid embeddings of planar graphs [PDF]
Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, 1992 Martin Fürer +3 more
openalex +2 more sources