Embedding Ray Intersection Graphs and Global Curve Simplification

Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

We prove that circle graphs (intersection graphs of circle chords) can be embedded as intersection graphs of rays in the plane with polynomial-size bit complexity. We use this embedding to show that the global curve simplification problem for the directed Hausdorff distance is NP-hard. In this problem, we are given a polygonal curve P and the goal is to find a second polygonal curve P′ such that the directed Hausdorff distance from P′ to P is at most a given constant, and the complexity of P′ is as small as possible.
Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization
Subtitle of host publication29th International Symposium, GD 2021, Tübingen, Germany, September 14–17, 2021, Revised Selected Papers
EditorsHelen C. Purchase, Ignaz Rutter
PublisherSpringer
Pages358–371
Number of pages14
Edition1
ISBN (Electronic)978-3-030-92931-2
ISBN (Print)978-3-030-92930-5
DOIs
Publication statusPublished - Sept 2021

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12868
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Embedding Ray Intersection Graphs and Global Curve Simplification'. Together they form a unique fingerprint.

Cite this