Pith. sign in

REVIEW 1 cited by

Integer realizations of disk and segment graphs

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1111.2931 v3 pith:4HCJHOUH submitted 2011-11-12 math.MG cs.CGmath.CO

classification math.MGcs.CGmath.CO
keywords graphdiskintegerdisksgraphseverysegmentrealized
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

A disk graph is the intersection graph of disks in the plane, a unit disk graph is the intersection graph of same radius disks in the plane, and a segment graph is an intersection graph of line segments in the plane. It can be seen that every disk graph can be realized by disks with centers on the integer grid and with integer radii; and similarly every unit disk graph can be realized by disks with centers on the integer grid and equal (integer) radius; and every segment graph can be realized by segments whose endpoints lie on the integer grid. Here we show that there exist disk graphs on $n$ vertices such that in every realization by integer disks at least one coordinate or radius is $2^{2^{\Omega(n)}}$ and on the other hand every disk graph can be realized by disks with integer coordinates and radii that are at most $2^{2^{O(n)}}$; and we show the analogous results for unit disk graphs and segment graphs. For (unit) disk graphs this answers a question of Spinrad, and for segment graphs this improves over a previous result by Kratochv\'{\i}l and Matou{\v{s}}ek.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal Curve Straightening is $\exists\mathbb{R}$-Complete

    cs.CG 2019-08 conditional novelty 6.0 of 10

    Optimal curve straightening to a target vertex count is ∃R-complete, and isotopy realization spaces of curves are universal up to homotopy equivalence.

Pith tools