Connected rectilinear graphs on point sets

M. Löffler, E. Mumford

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

5 Citations (Scopus)

Abstract

Given n points in d-dimensional space, we would like to connect the points with straight line segments to form a connected graph whose edges use d pairwise perpendicular directions. We prove that there exists at most one such set of directions. For d¿=¿2 we present an algorithm for computing these directions (if they exist) in O (n 2) time.
Original languageEnglish
Title of host publicationGraph Drawing (16th International Symposium, GD'08, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers)
EditorsI.G. Tollis, M. Patrignani
Place of PublicationBerlin
PublisherSpringer
Pages313-318
ISBN (Print)978-3-642-00218-2
DOIs
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
Volume5417
ISSN (Print)0302-9743

Cite this