{"id":{"repo_id":"denver","oai_identifier":"oai:digitalcommons.du.edu:etd-2420"},"canonical_url":"https://search.ndltd.org/etd/denver/oai:digitalcommons.du.edu:etd-2420","repository":{"repo_id":"denver","name":"University of Denver","base_url":"https://digitalcommons.du.edu/do/oai/"},"display":{"title":"On Barrier Graphs of Sensor Networks","abstract":"The study of sensor networks begins with a model, which usually has a geometric component. This thesis focuses on networks of sensors modeled as collections of rays in the plane whose use is to detect intruders, and in particular a graph derived from this geometry, called the barrier graph of the network, which captures information about the network's coverage. Every such ray-barrier sensor network corresponds to a barrier graph, but not every graph is the barrier graph of some network. We show that any barrier graph is not just tripartite, but perfect. We describe how to find networks which have certain designated graphs as their barrier graphs. We show that the size of a minimum vertex cover (in this context called the resilience) of a given graph can yield information about whether and how one can find a sensor network whose barrier graph is the given graph. Finally, we demonstrate that barrier graphs have certain strong structural properties, as a result of the geometry of ray-barrier networks, which represent progress towards a full characterization of barrier graphs.","abstract_html":"The study of sensor networks begins with a model, which usually has a geometric component. This thesis focuses on networks of sensors modeled as collections of rays in the plane whose use is to detect intruders, and in particular a graph derived from this geometry, called the barrier graph of the network, which captures information about the network&#x27;s coverage. Every such ray-barrier sensor network corresponds to a barrier graph, but not every graph is the barrier graph of some network. We show that any barrier graph is not just tripartite, but perfect. We describe how to find networks which have certain designated graphs as their barrier graphs. We show that the size of a minimum vertex cover (in this context called the resilience) of a given graph can yield information about whether and how one can find a sensor network whose barrier graph is the given graph. Finally, we demonstrate that barrier graphs have certain strong structural properties, as a result of the geometry of ray-barrier networks, which represent progress towards a full characterization of barrier graphs.","abstract_has_math":false,"creators":["Boyer, Kirk Anthony"],"institution":null,"degree_name":"M.S.","degree_level":"Masters Thesis","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Mario A. Lopez, Ph.D.","Paul Horn","Chris Gauthier-Dickey","Jing Li"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:52:26Z","subjects":["Barrier","Computational geometry","Coverage","Sensor networks","Computer Sciences","Other Computer Sciences"],"languages":["en"],"rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>","Kirk Anthony Boyer"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.du.edu/etd/1420","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.du.edu/etd/1420","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.du.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.du.edu%3Aetd-2420","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Mario A. Lopez, Ph.D.","Paul Horn","Chris Gauthier-Dickey","Jing Li"]},{"key":"dc:creator","label":"Author","values":["Boyer, Kirk Anthony"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2018-05-02T07:00:00Z"]},{"key":"dc:date.copyright","label":"Dc Date Copyright","values":["2017-01-01T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2017-01-01T08:00:00Z"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Barrier","Computational geometry","Coverage","Sensor networks","Computer Sciences","Other Computer Sciences"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"]},{"key":"dc:rights.holder","label":"Dc Rights Holder","values":["Kirk Anthony Boyer"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.du.edu/etd/1420"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The study of sensor networks begins with a model, which usually has a geometric component. This thesis focuses on networks of sensors modeled as collections of rays in the plane whose use is to detect intruders, and in particular a graph derived from this geometry, called the barrier graph of the network, which captures information about the network's coverage. Every such ray-barrier sensor network corresponds to a barrier graph, but not every graph is the barrier graph of some network. We show that any barrier graph is not just tripartite, but perfect. We describe how to find networks which have certain designated graphs as their barrier graphs. We show that the size of a minimum vertex cover (in this context called the resilience) of a given graph can yield information about whether and how one can find a sensor network whose barrier graph is the given graph. Finally, we demonstrate that barrier graphs have certain strong structural properties, as a result of the geometry of ray-barrier networks, which represent progress towards a full characterization of barrier graphs."]},{"key":"dc:description.provenance","label":"Dc Description Provenance","values":["Received from ProQuest"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["57 p."]},{"key":"dc:title","label":"Title","values":["On Barrier Graphs of Sensor Networks"]}]}],"canonical_facts":{"dc:contributor":["Mario A. Lopez, Ph.D.","Paul Horn","Chris Gauthier-Dickey","Jing Li"],"dc:creator":["Boyer, Kirk Anthony"],"dc:date.available":["2018-05-02T07:00:00Z"],"dc:date.copyright":["2017-01-01T08:00:00Z"],"dc:date.created":["2017-01-01T08:00:00Z"],"dc:description.abstract":["The study of sensor networks begins with a model, which usually has a geometric component. This thesis focuses on networks of sensors modeled as collections of rays in the plane whose use is to detect intruders, and in particular a graph derived from this geometry, called the barrier graph of the network, which captures information about the network's coverage. Every such ray-barrier sensor network corresponds to a barrier graph, but not every graph is the barrier graph of some network. We show that any barrier graph is not just tripartite, but perfect. We describe how to find networks which have certain designated graphs as their barrier graphs. We show that the size of a minimum vertex cover (in this context called the resilience) of a given graph can yield information about whether and how one can find a sensor network whose barrier graph is the given graph. Finally, we demonstrate that barrier graphs have certain strong structural properties, as a result of the geometry of ray-barrier networks, which represent progress towards a full characterization of barrier graphs."],"dc:description.provenance":["Received from ProQuest"],"dc:format":["application/pdf"],"dc:format.extent":["57 p."],"dc:identifier":["https://digitalcommons.du.edu/etd/1420"],"dc:language":["en"],"dc:rights":["<p>Copyright is held by the author. User is responsible for all copyright compliance.</p>"],"dc:rights.holder":["Kirk Anthony Boyer"],"dc:subject":["Barrier","Computational geometry","Coverage","Sensor networks","Computer Sciences","Other Computer Sciences"],"dc:title":["On Barrier Graphs of Sensor Networks"],"thesis:degree_level":["Masters Thesis"],"thesis:degree_name":["M.S."]},"updated_at":"2026-11-19T07:52:26Z"}