-shaped point set embeddings of high-degree plane graphs

Abstract

A point set embedding of a given plane graph on a given point set on a plane is a drawing of where each vertex is drawn on a point in . An orthogonal point set embedding of a plane graph is a point set embedding of such that each edge is drawn as a sequence of horizontal and vertical line segments. A plane graph of the maximum degree five or more does not admit an orthogonal point set embedding. To deal with plane graphs of the maximum degree five or more, in this paper we introduce “L-shaped point set embeddings”. An L-shaped point set embedding of a plane graph on a point set is a point set embedding of on such that each edge is drawn by a sequence of two straight-line segments which create a 90° angle at their common end. In this paper we consider -shaped point set embeddings of trees and Halin Graphs. Let be a point set of points on a plane such that no two points in lie on a horizontal or on a vertical line. We show that every tree of vertices as well as every Halin graph of vertices has an L-shaped point set embedding on .

Keywords

• point set embedding
• orthogonal point set embedding
• -shaped point set embedding