Concept

Slope number

In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as points in the Euclidean plane and edges are represented as line segments that do not pass through any non-incident vertex. Although closely related problems in discrete geometry had been studied earlier, e.g. by and , the problem of determining the slope number of a graph was introduced by , who showed that the slope number of an n-vertex complete graph Kn is exactly n. A drawing with this slope number may be formed by placing the vertices of the graph on a regular polygon. The slope number of a graph of maximum degree d is clearly at least , because at most two of the incident edges at a degree-d vertex can share a slope. More precisely, the slope number is at least equal to the linear arboricity of the graph, since the edges of a single slope must form a linear forest, and the linear arboricity in turn is at least . There exist graphs with maximum degree five that have arbitrarily large slope number. However, every graph of maximum degree three has slope number at most four; the result of for the complete graph K4 shows that this is tight. Not every set of four slopes is suitable for drawing all degree-3 graphs: a set of slopes is suitable for this purpose if and only if it forms the slopes of the sides and diagonals of a parallelogram. In particular, any degree 3 graph can be drawn so that its edges are either axis-parallel or parallel to the main diagonals of the integer lattice. It is not known whether graphs of maximum degree four have bounded or unbounded slope number. As showed, every planar graph has a planar straight-line drawing in which the number of distinct slopes is a function of the degree of the graph. Their proof follows a construction of for bounding the angular resolution of planar graphs as a function of degree, by completing the graph to a maximal planar graph without increasing its degree by more than a constant factor, and applying the circle packing theorem to represent this augmented graph as a collection of tangent circles.

About this result
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.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.