Compact Visibility Representation of 4-Connected Plane Graphs

The

visibility representation

(VR for short) is a classical representation of plane graphs. The VR has various applications and has been extensively studied. A main focus of the study is to minimize the size of the VR. It is known that there exists a plane graph

G

with

n

vertices where any VR of

G

requires a size at least

$\lfloor \frac{2n}{3} \rfloor \times (\lfloor \frac{4n}{3} \rfloor -3)$

. For upper bounds, it is known that every plane graph has a VR with size at most

$\lfloor \frac{2}{3}n \rfloor \times (2n-5)$

, and a VR with size at most

$(n-1) \times \lfloor \frac{4}{3}n \rfloor$

.

It has been an open problem to find a VR with both height and width simultaneously bounded away from the trivial upper bounds (namely of size

c

h

n

×

c

w

n

with

c

h

< 1 and

c

w

< 2). In this paper, we provide the first VR construction for a non-trivial graph class that simultaneously bounds both the height and the width. We prove that every 4-connected plane graph has a VR with height

$\leq \frac{3n}{4}+2\lceil\sqrt{n}\rceil +4$

and width

$\leq \lceil \frac{3n}{2}\rceil$

. Our VR algorithm is based on an

st

-orientation of 4-connected plane graphs with special properties. Since the

st

-orientation is a very useful concept in other applications, this result may be of independent interests.