Master’s Thesis Presentation • Algorithms and Complexity — Bounds on Maximum Matchings in 1-Planar GraphsExport this event to calendar

Monday, January 21, 2019 1:00 PM EST

John Wittnebel, Master’s candidate
David R. Cheriton School of Computer Science

In this thesis, we study lower bounds on maximum matchings in 1-planar graphs. We expand upon the tools used for proofs of matching bounds in other classes of graphs as well as some original ideas in order to find these bounds. The first novel results we provide are lower bounds of maximum matching in 1-planar graphs as a function of their minimum degree.

We show that for sufficiently large n, 1-planar graphs with minimum degree 3 have a maximum matching of size at least (n+12)/7, 1-planar graphs with minimum degree 4 have a maximum matching of size at least (n+4)/3, and 1-planar graphs with minimum degree 5 have a maximum matching of size at least (2n+3)/5. We also give examples of 1-planar graphs with the corresponding minimum degree that meet these bounds, showing that all of these bounds are tight. We also give examples of 1-planar graphs with small maximum matching and minimum degree 6 and 7. We conjecture that the 1-planar graph of minimum degree 6 presented has the smallest maximum matching over all 1-planar graphs of minimum degree 6, but it is unclear if the method used for the cases of minimum degree 3, 4, and 5 would work for minimum degree 6.

We also study lower bounds in the class of maximal 1-plane graphs, and 3-connected maximal 1-plane graphs. We find that 3-connected, maximal 1-plane graphs have a maximum matching of size at least (n+4)/3, and that maximal 1-plane graphs have a maximum matching of size at least (n+6)/4. Again, we present examples of such a graph to show this bound is tight. We also show that every simple 3-connected maximum 1-planar graph has a matching of size at least (2n+6)/5, and provide some evidence that this is tight.

Location 
DC - William G. Davis Computer Research Centre
2314
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2024 (96)
    1. April (19)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)