Advertisement
Published in:
2014 | OriginalPaper | Chapter
Unit Contact Representations of Grid Subgraphs with Regular Polytopes in 2D and 3D
Authors : Linda Kleist, Benjamin Rahman
Published in: Graph Drawing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 3
k
-gons of the hexagonal grid and UPCR with regular 4
k
-gons of the square grid.