We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 04 May 2018
Many results on the hardness of subconfiguration-related problems can be based on graph drawing algorithms that create configurations fromthe vertices and edges of a graph. The value of a monotone parameter of configurations, on a configuration generated from a graph, can often provide useful information about the graph that the configuration came from. If this information would allow us to solve a graph problem that is known to be hard, then computing the parametermust be hard as well.
Definitions
In this sectionwe briefly summarize the terminology fromgraph theory thatwe need here.
Definition 15.1 (graphs, vertices, and edges)
A graph, for our purposes, consists of a pair (V, E) where V is a finite set and E is a set of unordered pairs of elements of V. The elements of V are called vertices (a single one is a vertex) and the elements of E are called edges.1 The two vertices of each edge are called its endpoints. A vertex and edge are incident if the vertex is an endpoint of the edge. Two vertices are adjacent if they are both the endpoints of the same edge.
Definition 15.2 (graph drawings and planar graphs)
A drawing of a graph is a representation of the vertices by points in the plane and the edges by curves from one endpoint to the other that avoid the other vertices. A crossing in a drawing is a point where two edges intersect, other than at a shared endpoint of the edges. A drawing is planar if it has no crossings, and a graph is a planar graph if it can be drawn without crossings. Although, as mathematical objects, the vertices of a drawing are points, we will represent them in figures by small disks, as we do for other kinds of points (Figure 15.1).11
Definition 15.3 (paths and connectivity)
A path in a graph is an alternating sequence of vertices and edges, starting and ending with vertices, and with each consecutive pair of a vertex and an edge incident to each other. A graph is connected if every two vertices can be the first and last vertex of at least one path. An isolated vertex is a vertex that has no incident edges.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
