Pach, János (2016) Graphs with no grid obstacle representation. GEOMBINATORICS, XXVI (2). pp. 80-83. ISSN 1065-7371
|
Text
bishnugrid091917.pdf Download (40kB) | Preview |
Abstract
A graph G = ( V; E ) admits a grid obstacle representation , if there exist a subset Ω of the planar integer grid Z 2 and an embed- ding f : V ! Z 2 such that no vertex of G is mapped into a point of Ω , and two vertices u; v 2 V are connected by an edge of G if and only if there is a shortest path along the edges of Z 2 that con- nects f ( u ) and f ( v ) and avoids all other elements of Ω [ f ( V ) . We answer a question of Bishnu, Ghosh, Mathew, Mishra, and Paul, by showing that there exist graphs that do not admit a grid obstacle representation.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 28 Jan 2017 07:22 |
| Last Modified: | 28 Jan 2017 07:22 |
| URI: | http://real.mtak.hu/id/eprint/46726 |
Actions (login required)
 |
Edit Item |
