4 papers · 1 filter
Metric Planarity Testing is Hard
Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak +3
A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for…
Peeling Half the Onion: Embedding -Outerplanar Graphs into and Trees with a Polynomial Distortion (in )
Hsien-Chih Chang, Jonathan Conroy, William Eliot +2
Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that -outerplanar graphs can be embedded into trees and with distortion . Their result is pe…
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainl…
Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case where truly subquadratic-time algorithms…