**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Drawing Planar Graphs Of Bounded Degree With Few Slopes

Abstract

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different slopes. If we allow the edges to be represented by polygonal paths with one bend, then 2d slopes suffice. Allowing two bends per edge, every planar graph with maximum degree d >= 3 can be drawn using segments of at most [d/2] different slopes. There is only one exception: the graph formed by the edges of an octahedron is 4-regular, yet it requires 3 slopes. Every other planar graph requires exactly [d/2] slopes.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (3)

Drawing

Drawing is a visual art that uses an instrument to mark paper or another two-dimensional surface. The instrument might be pencils, crayons, pens with inks, brushes with paints, or combinations of these, and in more modern times, computer styluses with graphics tablets. A drawing instrument releases a small amount of material onto a surface, leaving a visible mark. The most common support for drawing is paper, although other materials, such as cardboard, vellum, wood, plastic, leather, canvas, and board, have been used.

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Slope

In mathematics, the slope or gradient of a line is a number that describes both the direction and the steepness of the line. Slope is often denoted by the letter m; there is no clear answer to the question why the letter m is used for slope, but its earliest use in English appears in O'Brien (1844) who wrote the equation of a straight line as and it can also be found in Todhunter (1888) who wrote it as "y = mx + c". Slope is calculated by finding the ratio of the "vertical change" to the "horizontal change" between (any) two distinct points on a line.