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

DOI10.1016/J.DISC.2014.05.001zbMATH Open1296.05139arXiv1307.1169OpenAlexW2026804159MaRDI QIDQ397151FDOQ397151

Authors: Tanya Khovanova, Jonathan Tidor, Jesse Geneson 

Publication date: 8 August 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• A note on visibility graphs
• Representing a planar graph by vertical lines joining different levels
• A Turán-type theorem on chords of a convex polygon
• On \(k\)-visibility graphs
• Further Results on Bar k-Visibility Graphs
• Title not available (Why is that?)
• Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer
• Bar k-Visibility Graphs
• Parameters of Bar k-Visibility Graphs

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)