Muutke küpsiste eelistusi

E-raamat: Crossing Numbers of Graphs

(DePaul University, Chicago, Illinois, USA)
Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 63,69 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Crossing Numbers of GraphsSuurem pilt
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

Crossing Numbers of Graphs is the first book devoted to the crossing number, an increasingly popular object of study with surprising connections. The field has matured into a large body of work, which includes identifiable core results and techniques. The book presents a wide variety of ideas and techniques in topological graph theory, discrete geometry, and computer science.

The first part of the text deals with traditional crossing number, crossing number values, crossing lemma, related parameters, computational complexity, and algorithms. The second part includes the rich history of alternative crossing numbers, the rectilinear crossing number, the pair crossing number, and the independent odd crossing number.It also includes applications of the crossing number outside topological graph theory.





Aimed at graduate students and professionals in both mathematics and computer science The first book of its kind devoted to the topic Authored by a noted authority in crossing numbers
Preface xvii
List of Figures
xxi
List of Tables
xxv
Symbol Description xxvi
I The Crossing Number
1(108)
1 The Conjectures of Zarankiewicz and Hill
3(30)
1.1 Drawings with Crossings
3(11)
1.1.1 A Puzzle
3(3)
1.1.2 Distinguishing Drawings of Graphs
6(4)
1.1.3 The Crossing Lemma
10(2)
1.1.4 The Parity Lemma
12(2)
1.2 Zarankiewicz and the Crossing Number of Complete Bipartite Graphs
14(7)
1.2.1 Exact Values
14(4)
1.2.2 Minimal Drawings
18(2)
1.2.3 Asymptotic Behavior
20(1)
1.3 Hill and the Crossing Number of Complete Graphs
21(9)
1.3.1 Exact Values
21(6)
1.3.2 Asymptotic Behavior
27(2)
1.3.3 Random Drawings
29(1)
1.4 Notes
30(1)
1.5 Exercises
31(2)
2 Drawings and Values
33(30)
2.1 Good Drawings of Complete Graphs
33(11)
2.1.1 Basic Properties
33(2)
2.1.2 Enumeration
35(2)
2.1.3 Extremal Properties
37(7)
2.2 Crossing Numbers of Graphs
44(15)
2.2.1 Cartesian Products of Graphs
44(2)
2.2.2 Cycles and the Harary-Kainen-Schwenk Conjecture
46(5)
2.2.2.1 The Hypercube
51(1)
2.2.3 More Complete Graphs
52(3)
2.2.4 Crossing-Critical Graphs
55(4)
2.3 Notes
59(1)
2.4 Exercises
59(4)
3 The Crossing Number and Other Parameters
63(24)
3.1 Bisection Width and Graph Layout
63(4)
3.2 Embeddings and Congestion
67(1)
3.3 Measures of Planarity
68(3)
3.3.1 Skewness
69(1)
3.3.2 Edge Crossing Number
70(1)
3.3.3 Thickness
70(1)
3.4 Chromatic Number and Albertson's Conjecture
71(2)
3.5 Beyond the Plane
73(11)
3.5.1 Genus
73(2)
3.5.2 Crossings on Surfaces
75(2)
3.5.3 Crossing Sequences
77(4)
3.5.4 Minors
81(3)
3.6 Notes
84(1)
3.7 Exercises
85(2)
4 Complexity and Algorithms
87(22)
4.1 The Hardness of Crossing Number Problems
87(4)
4.2 Drawing Graphs with Rotation
91(8)
4.2.1 How to Draw K2,n
91(5)
4.2.2 The Cyclic-Order Graphs
96(3)
4.3 Good Drawings of the Complete Graph
99(5)
4.3.1 Testing Goodness
99(3)
4.3.2 Gioan's Theorem
102(2)
4.4 Computing the Crossing Number
104(2)
4.5 Notes
106(1)
4.6 Exercises
107(2)
II Crossing Number Variants
109(186)
5 The Rectilinear Crossing Number: Rectilinear and Pseudolinear Drawings
111(26)
5.1 A First Look
111(4)
5.2 Pseudolines and the Pseudolinear Crossing Number
115(12)
5.2.1 Pseudolines and Wiring Diagrams
115(2)
5.2.2 Pseudolinear and Good Drawings
117(1)
5.2.3 Structure in Pseudolinear Drawings
118(3)
5.2.4 The Pseudolinear Crossing Number
121(1)
5.2.5 Stretchability and Complexity
121(3)
5.2.6 The Complexity of the Rectilinear Crossing Number
124(3)
5.3 Rectilinear Drawings
127(7)
5.3.1 Enumeration of Rectilinear Drawings
127(1)
5.3.2 Structure in Rectilinear Drawings
128(6)
5.4 Notes
134(1)
5.5 Exercises
134(3)
6 The Rectilinear Crossing Number: Values and Bounds
137(20)
6.1 A Look at the Complete Graph
137(16)
6.1.1 Sylvester's Four Point Problem
137(1)
6.1.2 Upper Bounds
138(5)
6.1.3 Lower Bounds and k-Edges
143(5)
6.1.4 Pseudolinear Drawings and Bishellability
148(5)
6.2 Other Graphs
153(2)
6.3 Notes
155(1)
6.4 Exercises
155(2)
7 The Local Crossing Number
157(24)
7.1 Local Crossings
157(7)
7.1.1 Simple, or Not?
157(1)
7.1.2 Density of Graphs with Few Local Crossings
158(4)
7.1.3 Local Crossings on Surfaces
162(2)
7.2 1-planarity
164(5)
7.2.1 A Map Coloring Problem
164(2)
7.2.2 Complexity of 1-Planarity Testing
166(3)
7.3 Rectilinear Drawings
169(8)
7.3.1 Rectilinear 1-planarity
169(5)
7.3.2 Rectilinear Local Crossing Number
174(3)
7.4 Quasi-k-planarity
177(2)
7.5 Notes
179(1)
7.6 Exercises
179(2)
8 Book and Monotone Crossing Numbers
181(24)
8.1 Embeddings and Drawings in Books
181(15)
8.1.1 Book Embeddings and Their Thickness
181(6)
8.1.2 A Single Page
187(1)
8.1.2.1 One-Page Drawings
187(3)
8.1.2.2 The Convex Crossing Number
190(2)
8.1.3 Two Pages
192(1)
8.1.4 The Book Crossing Number
193(3)
8.2 Monotonicity
196(6)
8.2.1 Monotone Drawings
196(2)
8.2.2 The Monotone Crossing Number
198(4)
8.3 Notes
202(1)
8.4 Exercises
203(2)
9 The Pair Crossing Number
205(16)
9.1 Counting Pairs
205(4)
9.2 A Crossing Lemma
209(2)
9.3 String Graphs
211(8)
9.3.1 A Separator Theorem
216(1)
9.3.2 Improving the pcr-Bound
217(2)
9.4 Notes
219(1)
9.5 Exercises
219(2)
10 The k-planar Crossing Number
221(14)
10.1 Drawing in k Planes
221(4)
10.2 Bounds and Values
225(6)
10.2.1 Complete Bipartite Graphs
225(5)
10.2.2 Complete Graphs
230(1)
10.2.3 Random Graphs
231(1)
10.3 Rectilinear and Geometric k-Planar Crossing Numbers
231(2)
10.4 Notes
233(1)
10.5 Exercises
233(2)
11 The Independent Odd Crossing Number
235(28)
11.1 Removing Even Crossings
235(4)
11.2 The Independent Odd Crossing Number
239(6)
11.2.1 An Algebraic Invariance of Good Drawings
239(2)
11.2.2 The Strong Hanani-Tutte Theorem
241(3)
11.2.3 A Crossing Lemma
244(1)
11.3 Lower Bounds on Odd Crossings
245(3)
11.4 Algebraic Crossing Numbers
248(2)
11.5 Separations
250(8)
11.5.1 Translating Separations
251(2)
11.5.2 Algebraic Crossings Matter
253(2)
11.5.3 Odd Crossings Matter
255(2)
11.5.4 Adjacent Crossings Matter
257(1)
11.6 Disjoint Edges in Topological Graphs
258(3)
11.7 Notes
261(1)
11.8 Exercises
261(2)
12 Maximum Crossing Numbers
263(32)
12.1 Polygons and Cycles
263(4)
12.2 Complete Graphs
267(1)
12.3 Thrackles
267(17)
12.3.1 The Thrackle Bound
267(2)
12.3.2 Conway's Thrackle Conjecture
269(2)
12.3.3 Generalized Thrackles
271(5)
12.3.4 Superthrackles
276(1)
12.3.5 A Better Bound
277(2)
12.3.6 Geometric and Monotone Thrackles
279(3)
12.3.7 The Subthrackle Bound
282(2)
12.4 The Subgraph Monotonicity Problem
284(4)
12.5 Hypercubes
288(1)
12.6 Complexity
289(1)
12.7 Notes
290(1)
12.8 Exercises
291(4)
III Appendices
295(20)
A Basics of Topological Graph Theory
297(12)
A.1 Curves
297(1)
A.2 Embeddings and Planar Graphs
298(3)
A.3 Bigons
301(1)
A.4 Graphs on Surfaces
302(2)
A.5 Rotations and Embedding Schemes
304(2)
A.6 Crossings in Drawings
306(1)
A.7 Notes
307(1)
A.8 Exercises
307(2)
B Basics of Complexity
309(6)
B.1 Algorithms, Time, and Space
309(1)
B.2 Computational Complexity
310(2)
B.3 Notes
312(1)
B.4 Exercises
312(3)
Bibliography 315(28)
Index 343
Marcus Schaefer received his undergraduate degree from the University of Karlsruhe, then his Ph.D. in Computer Science from the University of Chicago. After getting his doctorate, he has worked at the Computer Science Department of DePaul University in Chicago where he became an associate professor. His research interests include graph drawing, graph theory, computational complexity, and computability. He currently has 57 publications on MathSciNet. He also co-authored a book, Algorithms.
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97814987505092e.html
Märksõnad: