</noscript> <div id="header" class="row"> <nav class="top-bar eyebrow show-for-medium-up" data-topbar data-options="is_hover: false"> <section class="top-bar-section"> <div id="skiptocontent"><a href="#SkipTarget">skip to main content</a></div> <ul class="right"> <li><a href="http://www.acm.org" title="ACM Home">ACM Home</a></li> <li><a href="http://amturing.acm.org/" title="ACM A.M. Turing Award">ACM A.M. Turing Award</a></li> <li><a href="http://queue.acm.org" title="Queue">Queue</a></li> <li><a href="http://dl.acm.org" title="Digital Library">Digital Library</a></li> <li><a href="https://learning.acm.org" title="Learning Center">Learning Center</a></li> <li><a href="https://jobs.acm.org" title="Career Center">Career Center</a></li> </ul> </section> </nav> <div class="clearfix utilities-area"> <div class="logo-section"> <div class="navbar-header show-for-large-up"> <a class="navbar-brand" href="https://www.acm.org"> <img alt="ACM Logo" class="img-responsive" title="Home" src="/binaries/content/gallery/global/top-menu/acm_logo_tablet.svg"> </a> </div> <div class="navbar-header hide-for-large-up"> <a href="/"> <img alt="ACM Logo" class="img-responsive hide-for-large-up" title="Home" src="/binaries/content/gallery/global/top-menu/acm_logo_mobile.svg"> </a> </div> </div> <div id="acm-description" class="column large-5 show-for-large-up"> <div> Advancing Computing as a Science & Profession </div> </div> <div id="ctas-and-search" class="column large-5 medium-6 no-pad-left ctas-and-search"> <ul class="block-grid right"> <li><a href="http://www.acm.org/membership/join">Join</a></li> <li><a href="http://www.acm.org/about-acm/get-involved">Volunteer</a></li> <li><a href="/">Home</a></li> <li class="hide-for-small"> <form class="acm-search-form" id="form_1"> <label for="input_1"> <span class="visually-hidden">Search Input</span> </label> <input type="text" name="q" id="input_1" class="acm-searchbox-input st-default-search-input" /> <label for="search-site_1" class="toggle"> <span class="visually-hidden">Search Submit</span> <i class="fa fa-search left"></i> <input type="button" class="acm-searchbox-submit left" value="Search" name="search-site_1" id="search-site_1" /> </label> </form> </li> </ul> </div> </div> <script type="text/javascript"> (function(w,d,t,u,n,s,e){w['SwiftypeObject']=n;w[n]=w[n]||function(){ (w[n].q=w[n].q||[]).push(arguments);};s=d.createElement(t); e=d.getElementsByTagName(t)[0];s.async=1;s.src=u;e.parentNode.insertBefore(s,e); })(window,document,'script','//s.swiftypecdn.com/install/v2/st.js','_st'); _st('install','CQP6y65EjuZ71VuVBwbZ','2.0.0'); </script> <nav class="top-bar main-nav" data-topbar data-options="is_hover: false"> <ul class="title-area"> <li class="toggle-topbar menu-icon"><a href="/#"><span></span> </a></li> </ul> <section id="mobile-nav-topbar" class="top-bar-section"> <div class="mobile-links"> <div class="btn-group"> <a class="btn btn-primary" role="button" href="http://www.acm.org/membership/join">Join</a> <a class="btn btn-primary" role="button" href="http://www.acm.org/about-acm/get-involved">Volunteer</a> <a class="btn btn-primary" role="button" href="/">Home</a> </div> <div class="mobile-search"> <form class="acm-search-form" id="mobile_form_1"> <i class="fa fa-search left"></i> <label class for="search_mobile_1">Search</label> <input type="text" id="search_mobile_1" class="acm-searchbox-input st-default-search-input" name="q" /> </form> </div> </div> <ul> <li class="has-dropdown not-click"><a href="#">About ACM Speakers</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about" class="first">About ACM Speakers</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/about/purpose" title="Purpose">Purpose</a></li> <li><a href="/about/how-to" title="How To">How To</a></li> <li><a href="/about/policies" title="Policies">Policies</a></li> <li><a href="/about/nominate" title="Become or Nominate a Speaker">Become or Nominate a Speaker</a></li> <li><a href="/about/request" title="Request a Speaker">Request a Speaker</a></li> <li><a href="/calendar" title="Lectures Calendar">Lectures Calendar</a></li> <li><a href="/about/committee" title="ACM Speakers Committee">ACM Speakers Committee</a></li> <li><a href="https://campus2.acm.org/public/speakers/feedback.cfm" title="Feedback">Feedback</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Speakers</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/speakers" class="first">Browse Our Speakers</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/calendar" title="Lectures Calendar">Lectures Calendar</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Topics</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/topics" class="first">Browse Our Topics</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/calendar" title="Lectures Calendar">Lectures Calendar</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Countries</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/countries" class="first">Browse Countries in which Our Speakers Reside</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/calendar" title="Lectures Calendar">Lectures Calendar</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Request a Speaker</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/request" class="first">Request a Speaker</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Nominate a Speaker</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/nominate" class="first">Become or Nominate a Speaker</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Purpose</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/speakers-mission-and-history" class="first">Mission and History</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Governance</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/speakers-committee" class="first">Speakers Committee</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href="https://speakers.acm.org/speakers/lee_18369" target="_blank">Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href="/nominate"><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href="/nominate">Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> </ul> </section> </nav> </div> <div id="main"> <div class="article" id="maincontent" tabindex="-1"> <div class="row"> <div class="columns small-12"> <ul class="breadcrumbs"> <li><a href="/">Home</a></li> <li><a href="/lectures">Lectures</a></li> <li class="current">On Connectivity and Realizability of Triangle Cover Contact Graphs</li> </ul> </div> </div> <div class="speakers"> <div class="row lecture__section"> <h1>On Connectivity and Realizability of Triangle Cover Contact Graphs</h1> <span> <strong>Speaker: </strong> <a href="../speakers/rahman_20169">Md. Saidur Rahman</a> <span> – Dhaka, Bangladesh</span> </span><br/> <span> <strong>Topic(s): </strong> <a href="../topics/computational-theory-algorithms-and-mathematics">Computational Theory, Algorithms and Mathematics</a> </span> </div> <div class="row lecture__section"> <h2>Abstract</h2> Let S = {p1, p2, . . . , pn} be a set of pairwise disjoint geometric objects of some type in a 2D plane and let C = {c1, c2, . . . , cn} be a set of closed objects of some type in the same plane with the property that each element in C covers exactly one element in S and any two elements in C are interior-disjoint. We call an element in S a seed and an element in C a cover. A cover contact graph (CCG) has a vertex for each element of C and an edge between two vertices whenever the orresponding cover elements touch. Cover contact graphs have applications in VLSI layout, broadcast networks and in cartograms. In respect to cover contact graphs, “connectivity problems” and “realization problems” are studied by several researchers. In a connectivty problem it is asked to cover a given set of seeds by a set of covers such that the the resulting cover contact graph becomes k-connected. On the other hand in a realization problem we are given a graph G of n vertices and a set of n seeds and we are asked to determine whether there is any covering such that the resulting cover contact graph is G. It is known how to construct, for any given point seed set, a disk or triangle cover whose contact graph is 1- or 2-connected. The realization problem in general is known as NP-hard. In this talk I will present some of our recent results on triangle cover contact graphs and discuss some open problems. The talk is based on my joint works with Shaheena Sultana. </div> <div class="row lecture__section"> <h2>About this Lecture</h2> <span> <strong>Number of Slides: </strong> 70</span><br/> <span> <strong>Duration: </strong> 45 minutes </span><br/> <span> <strong>Languages Available: </strong> English</span><br/> <span> <strong>Last Updated: </strong> <span id="lecDate"></span> </span> </div> <div class="row lecture__section"> <h2>Request this Lecture</h2> <p>To request this particular lecture, please complete this <a href="https://services.acm.org/public/speakers/request_lecture.cfm?lecture_id=16391" target="_blank">online form.</a> </p> </div> <div class="row lecture__section"> <h2>Request a Tour</h2> <p>To request a tour with this speaker, please complete this <a href="https://services.acm.org/public/speakers/request_tour.cfm?lecturer_id=20169" target="_blank">online form.</a> </p> <p>All requests will be sent to ACM headquarters for review.</p> </div> </div> </div> <script> var updated = document.getElementById('lecDate'); var d = new Date(parseInt('1722384000000')); updated.innerHTML = d.getDate() + '/' + (d.getMonth() + 1) + '/' + d.getFullYear(); </script> </div> <div class="row"> <footer> <nav> <div class="footer-nav"> <ul class="footer-nav-lists"> <li> About ACM</li> <li><a href="https://www.acm.org/about-acm" title="About ACM">About ACM</a></li> <li><a href="https://www.acm.org/about-acm/get-involved" title="About ACM">Volunteer</a></li> </ul> <ul class="footer-nav-lists"> <li> Membership</li> <li><a href="https://www.acm.org/membership/join-acm" title="Membership">Join ACM</a></li> <li><a href="https://www.acm.org/membership/acm-membership-renewal" title="Membership">Renew My Membership</a></li> <li><a href="https://www.acm.org/membership/membership-options" title="Membership">Membership Options</a></li> <li><a href="https://www.acm.org/membership/membership-benefits" title="Membership">Membership Benefits</a></li> <li><a href="https://www.acm.org/membership/myacm-at-a-glance" title="Membership">myACM Sign-In</a></li> </ul> <ul class="footer-nav-lists"> <li> Publications</li> <li><a href="https://www.acm.org/publications" title="Publications">About Publications</a></li> <li><a href="https://www.acm.org/publications/digital-library" title="Publications">Digital Library</a></li> <li><a href="https://authors.acm.org/" title="Publications">Submit A Paper</a></li> </ul> <ul class="footer-nav-lists"> <li> Chapters</li> <li><a href="https://www.acm.org/chapters/chapter-administrative-interface" title="Chapters">Chapter Administrative Interface</a></li> <li><a href="https://www.acm.org/chapters/local-activities" title="Chapters">Chapter Activities Calendar</a></li> <li><a href="https://www.acm.org/chapters/start-chapter" title="Chapters">Start A Chapter</a></li> </ul> <ul class="footer-nav-lists"> <li> Awards</li> <li><a href="https://awards.acm.org" title="Awards">About ACM's Awards</a></li> </ul> <ul class="footer-nav-lists"> <li> Conferences</li> <li><a href="https://www.acm.org/conferences" title="Conferences">ACM's Conferences</a></li> </ul> <ul class="footer-nav-lists"> <li> Code of Ethics</li> <li><a href="https://www.acm.org/code-of-ethics" title="Code of Ethics">ACM's Code of Ethics</a></li> <li><a href="https://www.acm.org/code-of-ethics/enforcement-procedures" title="Code of Ethics">Enforcement Procedures</a></li> </ul> <ul class="footer-nav-lists"> <li> Media Center</li> <li><a href="https://www.acm.org/media-center" title="Media Center">ACM Media Center</a></li> </ul> </div> </nav> <div> <div> <div class="logo_social_group"> <hr/> <img src="/binaries/content/gallery/acm/logos/logo_footer_acm.png" alt="ACM Logo" /> <ul class="footer__social"> <li> <a href="https://www.facebook.com/AssociationForComputingMachinery/" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_facebook.png" alt="Facebook logo" /> </a> </li> <li> <a href="https://twitter.com/theofficialacm" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_x_twitter.png" alt="Twitter logo" /> </a> </li> <li> <a href="https://www.linkedin.com/company/association-for-computing-machinery" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_linkedin.png" alt="LinkedIn logo" /> </a> </li> <li> <a href="https://www.reddit.com/user/TheOfficialACM" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_reddit.png" alt="Reddit logo" /> </a> </li> <li> <a href="https://www.youtube.com/user/TheOfficialACM" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_youtube.png" alt="YouTube logo" /> </a> </li> <li> <a href="https://www.instagram.com/theofficialacm/" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_instagram.png" alt="Instagram" /> </a> </li> <li> <a href="https://www.flickr.com/photos/theofficialacm" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_flickr.png" alt="Flickr" /> </a> </li> <li> <a href="https://mastodon.acm.org/@ACM" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_mastodon.png" alt="Mastodon" /> </a> </li> </ul> </div> </div> </div> <div> <div> <ul class="footer__legal clearfix"> <li><a href="/">Home</a></li> <li><a href="/">SRC Home</a></li> <li><a href="https://www.acm.org">ACM Home</a></li> <li><a href="/sitemap">Sitemap</a></li> <li><a href="https://www.acm.org/about-acm/contact-us">Contact Us</a></li> <li><a href="https://www.acm.org/membership/acm-hq-contact">Member Services</a></li> <li><a href="https://www.acm.org/about-acm/privacy-policy">Privacy Policy</a></li> <li><a href="https://www.acm.org/accessibility">Accessibility</a></li> <li class="footer__copyright">Copyright © 2024, ACM, Inc</li> </ul> </div> </div> </footer> </div> <script data-cookieconsent="ignore" type="text/javascript" src="/js/acm.js?antiCache=1716999351349"></script> <script>$(document).foundation();</script> <script type="text/javascript" src="//s7.addthis.com/js/300/addthis_widget.js#pubid=ra-5654b74db1437702" async="async"></script> <script async src="https://www.googletagmanager.com/gtag/js?id=UA-115744816-1"></script> <script> window.dataLayer = window.dataLayer || []; function gtag(){ dataLayer.push(arguments); } gtag('js', new Date()); gtag('config', 'UA-115744816-1'); </script> </body> </html>