Theoretical results on at most 1-bend embeddability of graphs
type: Item
instance of: scholarly article
title: Theoretical results on at most 1-bend embeddability of graphs
zbMATH Open document ID: 0781.05015
DOI: 10.1007/BF02006154
author: Yanpei Liu
author: Paola Marchioro
author: Rossella Petreschi
author: Bruno Simeone
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 1993-05-25T00:00:00Z
review text: A planar graph is called \(k\)-rectilinear if it possesses an embedding in which every edge is a broken line consisting of at most \(k+1\) horizontal and vertical segments. The intersection of a horizontal and vertical segment of an edge is called a bend. It has been shown that every planar graph is 3-rectilinear. Every \(k\)-rectilinear graph has vertices with degree at most 4, so the study of such graphs can be restricted to planar graphs with degree 3 or 4. The authors call such graphs standard. There is no loss of generality in assuming that the graphs are 3-connected. If a standard graph has a standard dual, it is called bistandard. The paper under review gives forbidden subgraph characterizations of 1- rectilinear graphs for cubic planar, bistandard and self-dual bistandard graphs. For arbitrary 1-rectilinear graphs, there is a characterization by a countable family of forbidden subgraphs. A polynomial time algorithm constructs a 1-embedding if and only if one exists. Finally, there are upper bounds on the smallest total number of bends in 1-embeddings of planar cubic, planar bistandard, and self-dual bistandard graphs.
reviewed by: M.Marx
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 177986
zbMATH Keywords: \(k\)-rectilinear graph
zbMATH Keywords: planar graph
zbMATH Keywords: embedding
zbMATH Keywords: bend
zbMATH Keywords: characterizations
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: upper bounds
MaRDI profile type: Publication
cites work: General theoretical results on rectilinear embeddability of graphs
cites work: Boolean approach to planar embeddings of a graph
cites work: Single bend wiring
full work available at URL: https://doi.org/10.1007/bf02006154
OpenAlex ID: W2003764821
description: scientific article; zbMATH DE number 177986