Pixel and Voxel Representations of Graphs

摘要: We study contact representations for graphs, which we call pixel in 2D and voxel 3D. Our are based on the unit square grid whose cells pixels voxels Two adjacent if they share an edge, two a face. connected set of or blob. Given graph, represent its vertices by disjoint blobs such that contain only corresponding adjacent. interested size representation, is number it consists of. We first show finding minimum-size NP-complete. Then, bound representation sizes needed certain graph classes. In 2D, that, $k$-outerplanar graphs with $n$ vertices, $\Theta(kn)$ always sufficient sometimes necessary. particular, outerplanar can be represented linear pixels, whereas general planar need quadratic number. 3D, $\Theta(n^2)$ necessary any $n$-vertex graph. improve this to $\Theta(n\cdot \tau)$ treewidth $\tau$ $O((g+1)^2n\log^2n)$ genus $g$. admit $O(n\log^2n)$ voxels.