### Abstract

We study the exact complexity of the Hamiltonian Cycle and the q-Colouring problem in disk graphs. We show that the Hamiltonian Cycle problem can be solved in (formula presented) on n-vertex disk graphs where the ratio of the largest and smallest disk radius is O(1). We also show that this is optimal: assuming the Exponential Time Hypothesis, there is no (formula presented)-time algorithm for Hamiltonian Cycle, even on unit disk graphs. We give analogous results for graph colouring: under the Expo-nential Time Hypothesis, for any fixed q, q-Colouring does not admit a (formula presented)-time algorithm, even when restricted to unit disk graphs, and it is solvable in (formula presented)-time on disk graphs.

Original language | English |
---|---|

Title of host publication | Algorithms and Complexity |

Subtitle of host publication | 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings |

Editors | D. Fotakis, A. Pagourtzis, V.Th. Paschos |

Place of Publication | Dordrecht |

Publisher | Springer |

Pages | 369-380 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-319-57586-5 |

ISBN (Print) | 978-3-319-57585-8 |

DOIs | |

Publication status | Published - 2017 |

Event | 10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece Duration: 24 May 2017 → 26 May 2017 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10236 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 10th International Conference on Algorithms and Complexity, CIAC 2017 |
---|---|

Abbreviated title | CIAC 2017 |

Country | Greece |

City | Athens |

Period | 24/05/17 → 26/05/17 |

## Fingerprint Dive into the research topics of 'On the exact complexity of hamiltonian cycle and q-colouring in disk graphs'. Together they form a unique fingerprint.

## Cite this

*Algorithms and Complexity: 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings*(pp. 369-380). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10236 LNCS). Springer. https://doi.org/10.1007/978-3-319-57586-5_31