Results 11 to 20 of about 2,825 (206)
Straight line embeddings of cubic planar graphs with integer edge lengths [PDF]
Journal of Graph Theory, 2008 AbstractUnder what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle.
Jim Geelen, Anjie Guo, David McKinnon
openalex +13 more sources
Area-efficient planar straight-line drawings of outerplanar graphs
Discrete Applied Mathematics, 2007 AbstractIt is important to minimize the area of a drawing of a graph, so that the drawing can fit in a small drawing-space. It is well-known that a planar graph with n vertices admits a planar straight-line grid drawing with O(n2) area [H. de Fraysseix, J. Pach, R.
Ashim Garg, Adrian Rusu
openalex +3 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 +3 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 AbstractIn this paper we show that any maximal planar graph withmtriangles except the unbounded face can be transformed into a straight-line embedding in which at least ⌉m/3⌉ 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 ...
Atsushi Kaneko +2 more
openalex +3 more sources
On a Class of Planar Graphs with Straight-Line Grid Drawings on Linear Area
Journal of Graph Algorithms and Applications, 2009 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).
Md. Rezaul Karim, Md. Saidur Rahman
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 +3 more sources
Simultaneous straight-line drawing of a planar graph and its rectangular dual
, 2015 A natural way to represent on the plane both a planar graph and its dual is to follow the definition of the dual, thus, to place vertices inside their corresponding primal faces, and to draw the dual edges so that they only cross their corresponding primal edges.
Tamara Mchedlidze
openalex +4 more sources
An exact algorithm for disaster-resilience augmentation of planar straight-line graphs
Journal of Global OptimizationAbstract We consider the problem of adding a minimum length set of edges to a geometric graph so that the resultant graph is resilient against partition from the effect of a single disaster. Disasters are modeled by discs of given maximum radius, and a disaster destroys all edges intersecting its interior.
Alexander Westcott, Charl Ras
openalex +2 more sources
Study of Neural Network Algorithm for Straight-Line Drawings of Planar Graphs
, 2014 Graph drawing addresses the problem of finding a layout of a graph that satisfies given aesthetic and understandability objectives. The most important objective in graph drawing is minimization of the number of crossings in the drawing, as the aesthetics and readability of graph drawings depend on the number of edge crossings.
Mohamed A. El-Sayed +2 more
openalex +4 more sources
Augmenting Planar Straight Line Graphs to 2-Edge-Connectivity
, 2015 We show that every planar straight line graph PSLG with n vertices can be augmented to a 2-edge-connected PSLG with the addition of at most $$\lfloor 4n-4/3\rfloor $$ new edges. This bound is the best possible.
Hugo A. Akitaya +4 more
openalex +3 more sources