Unit Contact Representations of Grid Subgraphs with Regular Polytopes in 2D and 3D

Kleist, Linda and Rahman, Benjamin (2014) Unit Contact Representations of Grid Subgraphs with Regular Polytopes in 2D and 3D. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014 , pp. 137-148(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_12).

Full text not available from this repository.


We present a strategy to construct unit proper contact representations (UPCR) for subgraphs of certain highly symmetric grids. This strategy can be applied to obtain graphs admitting UPCRs with squares and cubes, whose recognition is NP-complete. We show that subgraphs of the square grid allow for UPCR with squares which strengthens the previously known cube representation. Indeed, we give UPCR for subgraphs of a d-dimensional grid with d-cubes. Additionally, we show that subgraphs of the triangular grid admit a UPCR with cubes, implying that the same holds for each subgraph of an Archimedean grid. Considering further polygons, we construct UPCR with regular 3k-gons of the hexagonal grid and UPCR with regular 4k-gons of the square grid.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_12
Classifications: G Algorithms and Complexity > G.560 Geometry
P Styles > P.060 3D
P Styles > P.999 Others
Z Theory > Z.500 Representations
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 09:02
Last Modified: 22 May 2015 09:02
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1428

Actions (login required)

View Item View Item