Faces in rectilinear drawings of complete graphs
By: Martin Balko , Anna Brötzner , Fabian Klute and more
Potential Business Impact:
Finds shapes in drawings of connected dots.
We initiate the study of extremal problems about faces in convex rectilinear drawings of~$K_n$, that is, drawings where vertices are represented by points in the plane in convex position and edges by line segments between the points representing the end-vertices. We show that if a convex rectilinear drawing of $K_n$ does not contain a common interior point of at least three edges, then there is always a face forming a convex 5-gon while there are such drawings without any face forming a convex $k$-gon with $k \geq 6$. A convex rectilinear drawing of $K_n$ is \emph{regular} if its vertices correspond to vertices of a regular convex $n$-gon. We characterize positive integers $n$ for which regular drawings of $K_n$ contain a face forming a convex 5-gon. To our knowledge, this type of problems has not been considered in the literature before and so we also pose several new natural open problems.
Similar Papers
Internally-Convex Drawings of Outerplanar Graphs in Small Area
Computational Geometry
Draws pictures of maps with less wasted space.
Stabbing Faces By a Convex Curve
Computational Geometry
Draws pictures where every inside space is cut by a curve.
Saturated Drawings of Geometric Thickness k
Computational Geometry
Draws pictures of connections with no extra lines.