Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs

DOI10.1016/J.DISC.2014.05.001MaRDI QIDQ397151zbMATH OpenOpenAlexFDO

Authors Tanya Khovanova, Jonathan Tidor, Jesse Geneson

Publication date 8 August 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.1169

zbMATH Keywords

geometric graphs\(k\)-quasiplanar graphs\(k\)-visibility graphsbar visibility graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We examine semi-bar visibility graphs in the plane and on a cylinder in which sightlines can pass through k objects. We show every semi-bar k-visibility graph has a (k+2)-quasiplanar representation in the plane with vertices drawn as points in convex position and edges drawn as segments. We also show that the graphs having cylindrical semi-bar k-visibility representations with semi-bars of different lengths are the same as the (2k+2)-degenerate graphs having edge-maximal (k+2)-quasiplanar representations in the plane with vertices drawn as points in convex position and edges drawn as segments.

Recommendations

• Parameters of Bar k-Visibility Graphs
• On \(k\)-visibility graphs
• Bar k-Visibility Graphs
• Further Results on Bar k-Visibility Graphs
• On 3D visibility representations of graphs with few crossings per edge

Cites work

• scientific article; zbMATH DE number 1744102 (Why is no real title available?)
• A Turán-type theorem on chords of a convex polygon
• A note on visibility graphs
• Bar k-Visibility Graphs
• Further Results on Bar k-Visibility Graphs
• Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer
• On \(k\)-visibility graphs
• Parameters of Bar k-Visibility Graphs
• Representing a planar graph by vertical lines joining different levels

Cited in

(2)

• Quasi-planar Graphs
• Beyond outerplanarity

This page was built for publication: Convex geometric \((k+2)\)-quasiplanar representations of semi-bar \(k\)-visibility graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q397151)