Thesis Abstract and Dissertation Abstracts
Crossing Number Of Graphs
Abstract Category: Engineering
Course / Degree: MAMathematics
Institution / University: Kalinga-Apayao State College, Philippines
Published in: 2012
This study focused on examining crossing number of graphs deals particularly on: 1) minimizing the crossing of edges when a drawing is defined, 2) establishing a relationship between the types of crossing numbers and 3) finding a bound on the crossing number of graphs.
A graph drawing is a mapping that assigns to each vertex a distinct point in the plane and to each edge UV a segment connecting ƒ(µ) and ƒ(v).A Petersen graph in a graph with │V(G)│= 10 and │E(G)│=15. A path Pn in a graph with an ordered list of distinct n ≥ 2 vertices V1 , V2 …, Vn such that Vi – 1Vi € E(Pn) for all 2 ≤ i < n. A cycle Cn is a graph with n ≥ 3 vertices say, V1 , V2 …, Vn , such that Vi – 1Vi € E(Cn) for all I = 2,3,…,n and Vn V1 € E(Cn). A complete graph is Kn is a graph with n ≥ 1 vertices such that every two distinct vertices are adjacent. A complete bipartite graph G: = (V1 + V2) is a bipartite graph such that for any two vertices V1 € V1 and V2 € V2 V1 V2 is an edge in G. A planar graph is a graph which can be embedded in the plane, i.e. it can be drawn in such a way that its edges intersect only at their endpoints. A subgraph of a graph G is a graph whose vertex set is a subset of that G, and whose adjacency relation is a subset of that of G restricted to this subset. The crossing number of G, denoted Cr(G), refers to the minimum number of G. the odd-crossing number, denoted odd-Cr(G), is the minimum number of pairs of edge (e,e’) such that e and e’ cross an odd number of times.
The crossing number of a simple undirected graph G, denoted Cr(G), refers to the minimum number of edge crossings in any drawing of G.
An immediate consequence of the definition of the crossing number is the fact that Cr(G) = 0 if and only if G is planar. This yields elementary results like Cr(Pn) = 0 and Cr(Cn) = 0.
Findings
In the process of minimizing edge crossings in the drawing of a graph G, the author was able to establish the following results:
1) Let G0 = (V, E0) G, where E0 denotes the collection of edges in G which cross any other edge at even number of times. Then
i) There is no vertex of degree 1 in G0.
ii) There are no two adjacent vertices of degree 2 in G0.
iii) In any subdivision of K5 or K3,3 contained in G, there are two paths representing independent edges, such that neither of them has edges all found in E0.
2) Let C be a cycle whose edges all come from E0 in a drawing (G, E0) of G. A connected subgraph B of G is a bridge of C if it consists of either a single edge whose endpoints belong to V(C), or of a connected component of G – V(C) together with all edges connecting it to C. Then G contains a cycle C (all edges come from E0) which has at least two bridges.
3) Let C denote a fixed cycle in G (with edges all found in E0) which has at least two bridges. Then C has exactly three bridges, at least one of which is a single edge.
4) Let C denote a fixed cycle in G (with edges all found in E0) which has at least two bridges. Then C has exactly three bridges, at least one of which is a single edge.
5) Let C denote a fixed cycle in G (with edges all found in E0). Then C has at least two bridges which are single edges.
With these observations, the following properties for the crossing number of a graph G were established:
1) For a fixed drawing of a graph G, let G0 G denote the subgraph formed by all even edges. Then G can be drawn in such a way that the edges belonging to G0 are not involved in any crossing.
2) The crossing number of any graph G satisfies
3) Let G be a graph with vertex set V(G) and edge set E(G) such that . Then
The author believes that for specific graphs, the crossing number is more definite, that is, a closed form formula can be obtained rather than just boundary values.
Paper Keywords/Search Tags:
Graphs , Crossing Number, Planar Graph
This Paper Abstract may be cited as follows:
Crossing Number of Graphs by Loneza G. Carbonel
Submission Details: Paper Abstract submitted by Loneza Carbonel from Philippines on 05-Apr-2013 04:00.
Abstract has been viewed 3279 times (since 7 Mar 2010).
Loneza Carbonel Contact Details: Email: loneza.carbonel@yahoo.com Phone: 09217785925
Disclaimer
Great care has been taken to ensure that this information is correct, however ThesisAbstracts.com cannot accept responsibility for the contents of this Paper abstract titled "Crossing Number Of Graphs". This abstract has been submitted by Loneza Carbonel on 05-Apr-2013 04:00. You may report a problem using the contact form.
© Copyright 2003 - 2024 of ThesisAbstracts.com and respective owners.