Theoretical results on at most 1-bend embeddability of graphs (Q1210238)

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.