pith. sign in

arxiv: 1810.07072 · v1 · pith:3Z4FNEXSnew · submitted 2018-10-16 · 💻 cs.CG

Segment representations with small resolution

classification 💻 cs.CG
keywords segmentgraphrepresentationrepresentationssegmentsgraphsgridplanar
0
0 comments X
read the original abstract

A segment representation of a graph is an assignment of line segments in 2D to the vertices in such a way that two segments intersect if and only if the corresponding vertices are adjacent. Not all graphs have such segment representations, but they exist, for example, for all planar graphs. In this note, we study the resolution that can be achieved for segment representations, presuming the ends of segments must be on integer grid points. We show that any planar graph (and more generally, any graph that has a so-called $L$-representation) has a segment representation in a grid of width and height $4^n$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.