Pith. sign in

REVIEW

Straight-line Drawability of a Planar Graph Plus an Edge

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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 1504.06540 v2 pith:AAY2NU2R submitted 2015-04-24 cs.CG

Straight-line Drawability of a Planar Graph Plus an Edge

Peter Eades , Seok-Hee Hong , Giuseppe Liotta , Naoki Katoh , Sheung-Hung Poon This is my paper
classification cs.CG
keywords drawingstraight-linegraphsalmost-planargraphalgorithmcharacterizationedge
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

We investigate straight-line drawings of topological graphs that consist of a planar graph plus one edge, also called almost-planar graphs. We present a characterization of such graphs that admit a straight-line drawing. The characterization enables a linear-time testing algorithm to determine whether an almost-planar graph admits a straight-line drawing, and a linear-time drawing algorithm that constructs such a drawing, if it exists. We also show that some almost-planar graphs require exponential area for a straight-line drawing.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.