Virginia Tech
    • Log in
    View Item 
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Doctoral Dissertations
    • View Item
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Doctoral Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Plane Permutations and their Applications to Graph Embeddings and Genome Rearrangements

    Thumbnail
    View/Open
    Chen_X_D_2017.pdf (766.5Kb)
    Downloads: 258
    Supporting documents (968.2Kb)
    Downloads: 35
    Date
    2017-04-27
    Author
    Chen, Xiaofeng
    Metadata
    Show full item record
    Abstract
    Maps have been extensively studied and are important in many research fields. A map is a 2-cell embedding of a graph on an orientable surface. Motivated by a new way to read the information provided by the skeleton of a map, we introduce new objects called plane permutations. Plane permutations not only provide new insight into enumeration of maps and related graph embedding problems, but they also provide a powerful framework to study less related genome rearrangement problems. As results, we refine and extend several existing results on enumeration of maps by counting plane permutations filtered by different criteria. In the spirit of the topological, graph theoretical study of graph embeddings, we study the behavior of graph embeddings under local changes. We obtain a local version of the interpolation theorem, local genus distribution as well as an easy-to-check necessary condition for a given embedding to be of minimum genus. Applying the plane permutation paradigm to genome rearrangement problems, we present a unified simple framework to study transposition distances and block-interchange distances of permutations as well as reversal distances of signed permutations. The essential idea is associating a plane permutation to a given permutation or signed permutation to sort, and then applying the developed plane permutation theory.
    URI
    http://hdl.handle.net/10919/77535
    Collections
    • Doctoral Dissertations [14977]

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us
     

     

    VTechWorks

    AboutPoliciesHelp

    Browse

    All of VTechWorksCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Log inRegister

    Statistics

    View Usage Statistics

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us